//力扣64. 最小路径和
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0&&j==0){
                    dp[i][j] = grid[i][j];
                    continue;
                }
                if(i==0){
                    dp[i][j] = grid[i][j] + dp[i][j-1];
                    continue;
                }
                if(j==0){
                    dp[i][j] = grid[i][j] + dp[i-1][j];
                    continue;
                }
                dp[i][j] = Math.min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);
            }
        }
        return dp[m-1][n-1];
    }
}


//力扣62. 不同路径
class Solution1 {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0||j==0){
                    dp[i][j]=1;
                    continue;
                }
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}


//5. 最长回文子串
class Solution2 {
    public String longestPalindrome(String s) {
        int n = s.length();
        // dp[i][j] 表示 i到j是否是回文串
        boolean[][] dp = new boolean[n + 1][n + 1];
        int res = 0;
        String str = ""; // 最终结果
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                //j - i <= 1说明是 一个字符 或者 是 两个连续相同的字符
                //dp[i + 1][j - 1]则看 i位置到j位置 之内是不是 回文串
                if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    res = Math.max(j - i, res);
                    if (j - i >= res) {
                        str = s.substring(i, j + 1); // 截取[i,j+1)位置的字符串
                    }
                }
            }
        }
        return str;
    }
}